1. Technical Field
The present invention generally relates to distributed computing, and more particularly to transaction processing. Specifically, the present invention relates to a method of searching a queue holding a series of requests for data processing tasks or transactions.
2. Description of Related Art
A queue is a line of items waiting for service in a system, such as tasks to be performed by a data processor. Associated with a queue is a queuing discipline that orders the entries in the queue according to some characteristic of the entries. Typical queuing disciplines include priority order, first in first out (FIFO), and last in first out (LIFO).
Service queues for data processing tasks typically employ a hybrid of the priority order and FIFO disciplines. The tasks are assigned respective priority levels so that a higher priority request placed in the queue after a lower priority request will be serviced first. Tasks in the same priority level, however, are serviced on a FIFO basis.
For some service queues, it is desirable to leave the task at the head of the queue while the task is being serviced, and remove it from the queue only after processing of the task has completed. If the task was not processed successfully, it may be transferred to an "error queue" prior to being removed from the service queue. Typically, the service queue is kept in nonvolatile or permanent memory so that in the event of a partial system failure, there will be a record of the task being performed at the time of the failure and a record of the tasks not yet performed. The results of the interrupted task can be inspected to determine whether that task completed, whether it can be restarted from an intermediate point, or whether it must be restarted from the beginning after intermediate results have been discarded. The remaining tasks on the queue can then be performed.
A very useful data structure known as a "key indexed file" is organized as a queue to provide both random and sequential access to data records. The data records are stored in a primary index structure ordered by a "primary key" and can also be retrieved through alternative index structures ordered by alternative keys. The alternative data structures do not contain data records; instead, they contain appropriate pointers to the data records. Software facilities for managing key indexed files typically provide the option of allowing two records to have the same keys; in this case, the records are stored or indexed so that they can be retrieved in first-in, first-out order. Therefore, service queues have been implemented as key indexed files by using a priority number as the primary key.
For data processing applications, and in particular distributed computing, a unique identification number is typically assigned to each task or transaction performed by a computer system. Also in such systems queues are typically used to transfer task data from one set of processors to another set of processors. In many applications it is desirable for the processing of a task to access the task data of another task, for example, to share data among tasks, to alter the priority of task execution, or to cancel tasks that have become unnecessary. To search a service queue for a specified task, the service queue could be a key indexed file using the task priority level as a primary key and using the task identification number as an alternate key. But using two keys decreases memory access speed because of the need to update the index for the alternate key any time a task is inserted or removed from the queue.